package medium

import (
	. "GoLeetcode/common"
)

/*
Bellman Ford（贝尔曼福德算法）: 计算经过的点或边的数量有限制的情况下的单源最短路径（可以求一个固定的点src到其他所有点的最短路径）
例如：从A到B最多经过k个中转点的最短路径 或者
	 从A到B最多经过k+1条边的最短路径

时间复杂度:O(k*(n+m)) 每次循环，clone切片复制的时间复杂度为O(N),遍历flights为O(M), k+1次循环
空间复杂度:O(n) 每次循环都需要创建一个clone切片

*/

func findCheapestPrice(n int, flights [][]int, src int, dst int, k int) int {
	// 1.初始化一个dst切片,dist[i]表示从起始点src到点i的最短路径
	// 初始化时，只将dst[src]置为0（src到src自己的距离是0）,其他全部设置为最大值(即表示初始状态src到i不经过任何边)
	// 所以当题目要求从A到B最多经过k个点(即k+1条边)时，外层循环循环k+1次而不是k次
	dist := make([]int, n+1)
	for i := 0; i < n; i++ {
		// 这里的无穷大为什么设置为0x3f3f3f3f:
		//		1.其10进制表示为1061109567, 10^9级别，满足一般题目的数据范围
		// 		2.0x3f3f3f3f+0x3f3f3f3f=2122219134 这个也是在int32范围内的，也就是说INF+INF还是等于无穷大且不会超范围
		// 参考: https://blog.csdn.net/jiange_zh/article/details/50198097
		dist[i] = INF
	}
	dist[src] = 0

	// 2.最外层循环是0->k+1 (表示最多经过k+1条边), 则dst[i]表示的是从src到i最多经过k+1条边时的单源最短路径
	for limit := 0; limit < k+1; limit++ {
		// 每次循环都需要记录上一次的结果，当前这一次循环求的是从src到i最多经过limit条边的最短路径,
		// 是从 src到i最多经过limit-1条边的最短路 推导而来的
		clone := make([]int, n+1)
		copy(clone, dist)
		// 3.松弛操作，src到j最多经过limit条边的最短路 由 src到i最多经过limit-1条边的最短路+从i直接到j的距离(只经过1条边) 推到而来
		for _, v := range flights {
			i, j, d := v[0], v[1], v[2]
			dist[j] = Min(dist[j], clone[i]+d)
		}
	}
	if dist[dst] >= INF {
		return -1
	}
	return dist[dst]
}
